//
// Created by Administrator on 2022/2/20.
//

#ifndef CPP_LEARNING_QUICKSORT_H
#define CPP_LEARNING_QUICKSORT_H

#include <iostream>
using Rank = int;


//[lo, hi)
template <class T>
void quickSort(T* elem, Rank lo, Rank hi){
    if(lo+1 >= hi) return;

    T pivot = elem[lo];
    Rank mid;

    int l = lo, r = hi-1;
    while (l < r){
        while (l < r && elem[r] >= pivot) r--;
        elem[l] = elem[r];

        while (l < r && elem[l] <= pivot) l++;
        elem[r] = elem[l];
    }

    elem[l] = pivot;

    for(int i=0;i < hi-lo; i++){
        std::cout<<elem[i + lo] << " " ;
    }
    std::cout<<std::endl;
    quickSort(elem,  lo, l);
    quickSort(elem,  l+1, hi);


}
#endif //CPP_LEARNING_QUICKSORT_H
